Relaxation is the core operation in Dijkstra's, updating distances when a shorter path is found.

  • Relaxation is the process of updating the distance to a node if we find a new, shorter path.
  • When we extract a node $u$ from the priority queue, we examine all its neighbors $v$.
  • We check if the path from the source *through* $u$ to $v$ is shorter than the *current* known distance to $v$.
  • The formal check uses the inequality: $d[u] + w(u, v) < d[v]$.
  • If the check is true, we update the distance: $d[v] = d[u] + w(u, v)$.
  • We also update the predecessor pointer: $previous[v] = u$.
  • The new, improved distance pair $(d[v], v)$ is then added back into the Priority Queue.
Python: Relaxation Logic

1# Inside the main loop, after getting current_node 'u'
2# current_distance = d[u]
3for neighbor, weight in G[u].items():
4    new_distance = current_distance + weight
5
6    # This is the "relaxation" check: d[u] + w(u, v) < d[v]
7    if new_distance < distances[neighbor]:
8        # Found a shorter path!
9        distances[neighbor] = new_distance
10        previous[neighbor] = u
11        heapq.heappush(pq, (new_distance, neighbor))